package org.laizili.solution.leetcode;

import org.laizili.structure.tree.bitree.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/range-sum-of-bst/">938. 二叉搜索树的范围和</a>
 * <p>
 * tags:二叉搜索树; 递归+剪枝
 */
public class Problem938 {
    private static class Solution {
        // 搜索+剪枝
        public int rangeSumBST(TreeNode root, int low, int high) {
            if (root == null) {
                return 0;
            }
            int sum;
            if (root.val < low)
                sum = rangeSumBST(root.right, low, high);
            else if (root.val > high)
                sum = rangeSumBST(root.left, low, high);
            else {
                sum = rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) + root.val;
            }
            return sum;
        }

    }
}
